/*
 * @Author: your name
 * @Date: 2021-07-06 08:08:02
 * @LastEditTime: 2021-07-06 13:05:59
 * @LastEditors: Please set LastEditors
 * @Description: In User Settings Edit
 * @FilePath: /mycode/mysort.cpp
 */

#include <iostream>
#include <algorithm>
#include <string>
#include <vector>

using namespace std;

//左闭右闭

void insertion_sort1(vector<int>& v,int n)
{
    int i,j;
    for(i=1;i<n;++i)
    {
        int temp=v[i];
        for(j=i;j>0&&temp<v[j-1];--j)
        {
            v[j]=v[j-1];//插入位置之后的有序序列整体后移
        }
        v[j]=temp;
    }
}
void insertion_sort2(vector<int>& v,int n)
{
    for(int i=1;i<n;i++)
    {
        for(int j=i;j>0&&v[j]<v[j-1];j--)
        {
            swap(v[j],v[j-1]);
        }
    }
}
void shellsort(vector<int>& v,int n)
{
    for(int gap=n/2;gap>0;gap/=2)//确定当前步长
    {
        for(int i=gap;i<n;i++)//以该步长为基础，分成了多少个序列
        {
            int temp=v[i];//不是v[gap]
            int j;
            for(j=i;j>=gap&&v[j-gap]>temp;j-=gap)//插入排序基操
                v[j]=v[j-gap];
            v[j]=temp;
        }
    }
}

void selection_sort(vector<int> &v,int n)
{
    for(int i=0;i<n;i++)//进行n轮，每轮确定一个最小元素，属于交换类排序
    {
        int index=i;//index为无序序列中最小元素的下标
        for(int j=i;j<n;j++)
        {
            if(v[j]<v[index])
                index=j;
        }
        swap(v[index],v[i]);
    }
}
//插入排序、希尔排序、选择排序、冒泡排序、归并排序、快速排序、桶排序、基数排序、堆排序、bogo排序
void bubble_sort(vector<int> &v ,int n)
{
    bool flag=true;
    int k=0;
    while(flag)
    {
        flag=false;
        for(int i=1;i<n-k;i++)
        {
            if(v[i]<v[i-1])
            {
                swap(v[i],v[i-1]);
                flag=true;
            }
        }
        k++;
    }
}

void quicksort(vector<int> &v,int l,int r)//分治算法，快排的核心是分区
{
    if(l>=r)
        return ;
    int a=l;
    int b=r-1;
    int key=v[a];
    while(a<b)
    {
        while(a<b&& v[b]>=key)
            b--;
        v[a]=v[b];

        while(a<b && v[a]<=key)
            a++;
        v[b]=v[a];
    }
    v[a]=key;
    quicksort(v,0,a);
    quicksort(v,a+1,b+1);//左闭右闭
}

void merge(vector<int> &v,int l,int m,int r)
{
    int i,j,k;
    int n1=m-l+1;//左序列长度
    int n2=r-m;//右序列长度
    int L[n1],R[n2];
    for(i=0;i<n1;i++)
    {
        L[i]=v[l+i];
    }
    for(j=0;j<n2;j++)
    {
        R[j]=v[m+1+j];
    }
    i=0;
    j=0;
    k=l;
    while(i<n1&&j<n2)
    {
        if(L[i]<=R[j])
        {
            v[k++]=L[i++];
        }
        else if(L[i]>R[j])
        {
            v[k++]=R[j++];
        }
    }
    while(i<n1)
        v[k++]=L[i++];
    while(j<n2)
        v[k++]=R[j++];
}
void mergesort(vector<int> &v,int l,int r)
{
    if(l>=r)
        return ;
    int m=l+(r-l)/2;
    mergesort(v,l,m);
    mergesort(v,m+1,r);
    merge(v,l,m,r);//为什么这句要放最后？
}

void heapify(vector<int> &arr, int n, int i) //什么功能？建堆
{ 
    int largest = i; // 将最大元素设置为堆顶元素
    int l = 2*i + 1; // left = 2*i + 1 
    int r = 2*i + 2; // right = 2*i + 2 
  
    // 如果 left 比 root 大的话
    if (l < n && arr[l] > arr[largest]) 
        largest = l; 
  
    // I如果 right 比 root 大的话
    if (r < n && arr[r] > arr[largest]) 
        largest = r; 
  
    if (largest != i) 
    { 
        swap(arr[i], arr[largest]); 
  
        // 递归地定义子堆
        heapify(arr, n, largest); 
    } 
} 
void heapsort(vector<int> &arr, int n) //arr错误，&arr正确
{ 
    // 建立堆
    for (int i = n / 2 - 1; i >= 0; i--) 
        heapify(arr, n, i); 
  
    // 一个个从堆顶取出元素
    for (int i=n-1; i>=0; i--) 
    { 
        swap(arr[0], arr[i]);  
        heapify(arr, i, 0); 
    } 
} 

void bucketSort(vector<int> arr, int n) 
{ 
    // 1) Create n empty buckets 
    vector<int> b[n]; 
     
    // 2) Put array elements in different buckets 
    for (int i=0; i<n; i++) 
    { 
       int bi = n*arr[i]; // Index in bucket 
       b[bi].push_back(arr[i]); 
    } 
  
    // 3) Sort individual buckets 
    for (int i=0; i<n; i++) 
       sort(b[i].begin(), b[i].end()); 
  
    // 4) Concatenate all buckets into arr[] 
    int index = 0; 
    for (int i = 0; i < n; i++) 
        for (int j = 0; j < b[i].size(); j++) 
          arr[index++] = b[i][j]; 
}

int getMax(vector<int> &arr, int n) 
{ 
    int mx = arr[0]; 
    for (int i = 1; i < n; i++) 
        if (arr[i] > mx) 
            mx = arr[i]; 
    return mx; 
} 

void countSort(vector<int> &arr, int n, int exp) 
{ 
    int output[n]; 
    int i, count[10] = {0}; 
  
    for (i = 0; i < n; i++) 
        count[ (arr[i]/exp)%10 ]++; 
  
    for (i = 1; i < 10; i++) 
        count[i] += count[i - 1]; 
  
    for (i = n - 1; i >= 0; i--) 
    { 
        output[count[ (arr[i]/exp)%10 ] - 1] = arr[i]; 
        count[ (arr[i]/exp)%10 ]--; 
    } 
  
    for (i = 0; i < n; i++) 
        arr[i] = output[i]; 
} 
  
void radixsort(vector<int> &arr, int n) 
{ 
    int m = getMax(arr, n); 
    for (int exp = 1; m/exp > 0; exp *= 10) 
        countSort(arr, n, exp); 
} 

int main()
{
    vector<int> v{2,3,1,6,4,7,9,8,-9,34,0};
    //vector<int> v{7,1,4};
    vector<int> t(v);
    int temp;
    /*while(cin>>temp)
    {
        v.push_back(temp);
    }*/
    cout<<"排序之前："<<endl;
    for(auto &a:v)
        cout<<a<<" ";

    //quicksort(v,0,v.size());
    //mergesort(v,0,v.size()-1);//注意传参的值；
    //bubble_sort(v,v.size());
    //selection_sort(v,v.size());
    //insertion_sort1(v,v.size());
    //insertion_sort2(v,v.size());
    //shellsort(v,v.size());
    //heapsort(v,v.size());
    bucketSort(v,v.size());
    //radixsort(v,v.size());
    cout<<endl;
    cout<<"排序之后："<<endl;
    for(auto &a:v)
        cout<<a<<" ";
    cout<<"\n";//不加这一行有百分号
    return 0;
}